package _11_整理题目._7_查找排序;

import org.junit.Test;

import java.util.Arrays;

/**
 * 总题解：https://leetcode-cn.com/problems/search-rotate-array-lcci/solution/xuan-zhuan-shu-zu-cong-yi-dao-nan-ge-ge-dcv7a/
 * 
 * https://leetcode-cn.com/problems/rotate-array/
 * 给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。
 *
 * 进阶：
 *
 * 尽可能想出更多的解决方案，至少有三种不同的方法可以解决这个问题。
 * 你可以使用空间复杂度为 o(1) 原地算法解决这个问题吗？
 *
 * 1、逐个移动
 * 2、翻转三次
 * 
 */
public class _20_旋转数组 {
    
    public void rotate(int[] nums, int k) {
        int n = nums.length;
        k %= n;
        reverse(nums, 0, n-1);
        reverse(nums, 0, k-1);
        reverse(nums, k, n-1);
    }
    public void reverse(int[] nums, int star, int end) {
        while(star < end) {
            int tmp = nums[star];
            nums[star] = nums[end];
            nums[end] = tmp;
            star++; end--;
        }
    }
    
    @Test
    public void main() {
        int[] input = {1,2,3,4,5,6};
        System.out.println(Arrays.toString(input));
        rotate(input, 8);
        System.out.println(Arrays.toString(input));
    }
    
}
